Micron Document
<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>Einfacher Graph</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/Einfacher_Graph"> <link href="./_mw_/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Einfacher_Graph rootpage-Einfacher_Graph skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Einfacher Graph</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Ein <b>einfacher Graph</b> (auch <b>schlichter Graph</b>) ist in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> ein <a href="Ungerichteter_Graph" class="mw-redirect" title="Ungerichteter Graph">ungerichteter Graph</a> ohne <a href="Mehrfachkante" class="mw-redirect" title="Mehrfachkante">Mehrfachkanten</a> und ohne <a href="Schleife_(Graphentheorie)" title="Schleife (Graphentheorie)">Schleifen</a>.
</p><p>Ein einfacher Graph ist also ein geordnetes Paar <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (V,E)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mi>V</mi>
<mo>,</mo>
<mi>E</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (V,E)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a01724c7d662052bd5f1c34cb725c8001634069a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.406ex; height:2.843ex;" alt="{\displaystyle (V,E)}" loading="lazy"></span>, wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>V</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle V}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"></span> eine Menge von <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>E</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle E}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"></span> eine Menge von <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> ist. Die Menge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>E</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle E}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"></span> ist dabei eine Menge von 2-elementigen Teilmengen von&nbsp;<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>V</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle V}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"></span>.
</p><p>Ein einfacher Graph mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Knoten kann demzufolge maximal <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle {n \choose 2}={\frac {n(n-1)}{2}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mstyle displaystyle="false" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mrow class="MJX-TeXAtom-OPEN">
<mo maxsize="1.2em" minsize="1.2em">(</mo>
</mrow>
<mfrac linethickness="0">
<mi>n</mi>
<mn>2</mn>
</mfrac>
<mrow class="MJX-TeXAtom-CLOSE">
<mo maxsize="1.2em" minsize="1.2em">)</mo>
</mrow>
</mrow>
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mi>n</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
</mrow>
<mn>2</mn>
</mfrac>
</mrow>
</mstyle>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \textstyle {n \choose 2}={\frac {n(n-1)}{2}}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b24c054b10c7d1410650585b0059ae001c098c00.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:12.403ex; height:4.176ex;" alt="{\displaystyle \textstyle {n \choose 2}={\frac {n(n-1)}{2}}}" loading="lazy"></span> Kanten haben. Sind alle diese Kanten vorhanden, wird der Graph als <a href="Vollst%C3%A4ndiger_Graph" title="Vollständiger Graph">vollständiger Graph</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>K</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle K_{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ea2b988ea630d2c5571afe47efa3d3b251708acb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.192ex; height:2.509ex;" alt="{\displaystyle K_{n}}" loading="lazy"></span> bezeichnet.
</p><p>Wenn die Kanten des Graphen zusätzlich mit Werten versehen sind (z.&nbsp;B. Entfernungen), spricht man von einer Gewichtung (auch Bewertung) der Kanten und dann von einem <a href="Kantengewichteter_Graph" title="Kantengewichteter Graph">kantengewichteten Graphen</a>.
</p>
<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

<p>Die Nachbarschaftsbeziehungen zwischen <a href="Deutschland" title="Deutschland">Deutschland</a> und seinen Nachbarländern können als einfacher Graph <a href="Modell" title="Modell">modelliert</a> werden. In diesem Beispiel umfasst die Menge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>V</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle V}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"></span> die Länder und jede Kante steht dafür, dass zwei Länder benachbart sind. In der nebenstehenden Abbildung wird dieser Graph dargestellt, wobei die Knoten als Punkte und die Kanten als Verbindungslinien gezeichnet sind. Man beachte, dass der Graph nur die bestehenden Beziehungen umfasst, dagegen sind Position und Größe der Knoten und Kanten frei gewählt.
</p><p>Betrachtet man die formale Definition des Graphen als Paar <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (V,E)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mi>V</mi>
<mo>,</mo>
<mi>E</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (V,E)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a01724c7d662052bd5f1c34cb725c8001634069a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.406ex; height:2.843ex;" alt="{\displaystyle (V,E)}" loading="lazy"></span> dann ist die Knotenmenge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>V</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle V}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"></span> also durch die Menge {Belgien, Dänemark, Deutschland, Frankreich, Luxemburg, Niederlande, Österreich, Polen, Schweiz, Tschechische Republik} gegeben. Beispiele für Kanten in der Menge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>E</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle E}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"></span> sind {Belgien, Deutschland}, {Österreich, Schweiz} und {Deutschland, Polen}.
Dabei bezeichnen {Belgien, Deutschland} und {Deutschland, Belgien} dieselbe Kante.
</p>
<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>
<ul><li><a href="Dieter_Jungnickel" title="Dieter Jungnickel">Dieter Jungnickel</a>: <cite style="font-style:italic">Graphen, Netzwerke und Algorithmen</cite>. 3. Auflage. BI Wissenschaftsverlag, 1994, ISBN 3-411-14263-4.<span class="Z3988" title="ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rfr_id=info:sid/de.wikipedia.org:Einfacher+Graph&amp;rft.au=Dieter+Jungnickel&amp;rft.btitle=Graphen%2C+Netzwerke+und+Algorithmen&amp;rft.date=1994&amp;rft.edition=3&amp;rft.genre=book&amp;rft.isbn=3411142634&amp;rft.pub=BI+Wissenschaftsverlag" style="display:none">&nbsp;</span></li></ul>
<ul><li><a href="Eric_Weisstein" title="Eric Weisstein">Eric W. Weisstein</a>: <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/SimpleGraph.html"><i>Simple Graph</i>.</a> In: <i><a href="MathWorld" title="MathWorld">MathWorld</a></i> (englisch).</li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-03-24" href="https://de.wikipedia.org/wiki/?title=Einfacher_Graph&amp;oldid=254494433">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>

</body></html>